COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a28.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Greibach's Theorem\hfill}

Let $G$ be a CFG where no right hand side 
is in $\{\epsilon\}\cup V$. We already know
that all CFGs can be put in this form, without altering their languages
except by omitting~$\epsilon$.
Assume $V↓G=\{A↓i\}$. Define a grammar~$G'$, with variables
$V'=\{A↓i\}\cup\{B↓{ij}\}$. Define the productions~$P'$ of~$G'$ as follows:

\smallskip
\disleft 20pt:(1):
For each $A↓i→A↓j\beta$ in $P$, $B↓{kj}→\beta B↓{ki}$ is in~$P'$ for all~$k$.

\smallskip
\disleft 20pt:(2):
For each $A↓i→t\gamma$ in $P$, $A↓k→t\gamma B↓{ki}$ is in $P'$ for all~$k$.

\smallskip
\disleft 20pt:(3):
For all $i$, $B↓{ii}→\epsilon$ is in $P'$.

\smallskip
\disleft 20pt:(4):
That's all.

\noindent
(Subscripts, above, are taken from some finite set.)

\proclaim Theorem. $A↓i\aRag u$ iff $A↓i\aRagp u$.

\vfill\eject

\noindent
{\bf Part 1:} Assume $A↓i\aRag u$. Because $A↓i$ is a variable, and $u$
contains no variables, using the partition theorem we can assume that the
derivation begins by applying productions to the first symbol (at least once)
until it is terminal. Then the first part of the derivation is, say,
$$\vcenter{\halign{\hfil$#$\qquad&$#$\hfil\cr
\hbox{String}&\hbox{Production}\cr
\noalign{\smallskip}
A↓0\cr
&A↓0→A↓1\beta↓1\cr
A↓1\beta↓1\cr
&A↓1→A↓2\beta↓2\cr
A↓2\beta↓2\beta↓1\cr
&A↓2→A↓3\beta↓3\cr
A↓3\beta↓3\beta↓2\beta↓1\cr
&A↓3→A↓4\beta↓4\cr
A↓4\beta↓4\beta↓3\beta↓2\beta↓1\cr
&A↓4→t\gamma\cr
t\gamma\beta↓4\beta↓3\beta↓2\beta↓1\cr
\noalign{\medskip}
\noalign{\hbox{But the same derivation in $G'$ is}\hfil}
A↓0\cr
&A↓0→t\gamma B↓{04}\cr
t\gamma B↓{04}\cr
&B↓{04}→\beta↓4B↓{03}\cr
t\gamma\beta↓4 B↓{03}\cr
&B↓{03}→\beta↓3B↓{02}\cr
t\gamma\beta↓4\beta↓3 B↓{02}\cr
&B↓{02}→\beta↓2B↓{01}\cr
t\gamma\beta↓4\beta↓3\beta↓2 B↓{01}\cr
&B↓{01}→\beta↓1B↓{00}\cr
t\gamma\beta↓4\beta↓3\beta↓2\beta↓1 B↓{00}\cr
&B↓{00}→\epsilon\cr
t\gamma\beta↓4\beta↓3\beta↓2\beta↓1\cr}}$$
and, by the partition theorem and course-of-values induction, if
$t\gamma\beta↓4\beta↓3\beta↓2\beta↓1\aRag u$,
$t\gamma\beta↓4\beta↓3\beta↓2\beta↓1\aRagp u$.

\vfill\eject

\noindent
{\bf Part 2:} Assume $A↓i\aRagp u$. Then the derivation must begin with a
production from part~(2), and by rewriting the rightmost symbol until it
is no longer~a~$B$, we get as a typical derivation:
$$\vcenter{\halign{\hfil$#$\qquad&$#$\hfil\qquad&$#$\hfil\cr
\hbox{String}\quad&\hbox{Production in $G'$}&\hbox{From production in $G$}\cr
\noalign{\smallskip}
A↓0\cr
&A↓0→t\gamma B↓{04}&A↓4→t\gamma\cr
t\gamma B↓{04}\cr
&B↓{04}→\beta↓4B↓{03}&A↓3→A↓4\beta↓4\cr
t\gamma\beta↓4 B↓{03}\cr
&B↓{03}→\beta↓3B↓{02}&A↓2→A↓3\beta↓3\cr
t\gamma\beta↓4\beta↓3 B↓{02}\cr
&B↓{02}→\beta↓2B↓{01}&A↓1→A↓2\beta↓2\cr
t\gamma\beta↓4\beta↓3\beta↓2 B↓{01}\cr
&B↓{01}→\beta↓1B↓{00}&A↓0→A↓1\beta↓1\cr
t\gamma\beta↓4\beta↓3\beta↓2\beta↓1 B↓{00}\cr
&B↓{00}→\epsilon\cr
t\gamma\beta↓4\beta↓3\beta↓2\beta↓1\cr}}$$
But the productions of $G'$ we have used imply the existence of the
productions of~$G$, above, that derive the same string. Again by the
partition theorem and course-of-values induction, $A↓i\aRag u$. In particular,
$S\aRag u$ iff $S\aRagp u$, so the languages are the same.

In the above construction, all the strings called~$\beta$ are in~$V↑+$, so all
productions of~$G'$ are of the forms:
$$\eqalign{B↓{ij}&→A↓k\,\alpha↓1|t\alpha↓1\cr
A↓k&→t\,\alpha↓2\cr
B↓{ii}&→\epsilon\cr}$$
and eliminating $\epsilon$ as a right side leaves the forms
$$\eqalign{B↓{ij}&→A↓k\,\alpha↓1|t\alpha↓1\cr
A↓k&→t\,\alpha↓2\,.\cr}$$
Eliminating $A$'s as the first character on the right, we get forms
$$\eqalign{B↓{ij}&→t\,\alpha↓2\,\alpha↓1\cr
A↓k&→t\,\alpha↓2\cr}$$
where each right side begins with a terminal symbol. This is the major
result of Greibach's theorem, the rest of which is a drill:

\proclaim Theorem. For every CFL, there is a CFG in which 
$P\subseteq V\times (T\otimes V↑{\ast})$. 

We have already shown
$P\subseteq V\times (T\otimes\Sigma↑{\ast})$.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd
First draft (not published)
May 2, 1986.
%revised date;
%subsequently revised.

\bye